struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
  ListNode *partition(ListNode *head, int x) {
    ListNode head1{0, nullptr}, head2{0, nullptr};
    ListNode *tailPtr1 = &head1, *tailPtr2 = &head2;
    for (; head != nullptr; head = head->next) {
      if (head->val < x) {
        tailPtr1->next = head;
        tailPtr1 = tailPtr1->next;
      } else {
        tailPtr2->next = head;
        tailPtr2 = tailPtr2->next;
      }
    }
    tailPtr1->next = head2.next;
    tailPtr2->next = nullptr;
    return head1.next;
  }
};
